package org.labuladong.暴力搜索算法.回溯算法;

import java.util.LinkedList;
import java.util.List;

/**
 * @Author: qingle
 * @Date: 2024/10/28-16:11
 * @Description: 46. 全排列
 * @version: 1.0
 */
public class LC_46__全排列 {

//	class Solution {
		List<List<Integer>> res = new LinkedList<>();
		/* 主函数，输⼊⼀组不重复的数字，返回它们的全排列 */
		public List<List<Integer>> permute(int[] nums) {
			// 记录「路径」
			LinkedList<Integer> track = new LinkedList<>();
			backtrack(nums, track);
			return res;
		}
		void backtrack(int[] nums, LinkedList<Integer> track) {
			// 触发结束条件
			if (track.size() == nums.length) {
				res.add(new LinkedList(track));
				return;
			}
			for (int i = 0; i < nums.length; i++) {
				// 排除不合法的选择
				if (track.contains(nums[i])) {
					continue;
				}
				// 做选择
				track.add(nums[i]);
				// 进⼊下⼀层决策树
				backtrack(nums, track);
				// 取消选择
				track.removeLast();
			}
		}
//	}
}
